Skip to main content

3354. Make Array Elements Equal to Zero

Easy
Description

You are given an integer array nums.

Start by selecting a starting position curr such that nums[curr] == 0, and choose a movement direction of either left or right.

After that, you repeat the following process:

If curr is out of the range [0, n - 1], this process ends. If nums[curr] == 0, move in the current direction by incrementing curr if you are moving right, or decrementing curr if you are moving left. Else if nums[curr] > 0: Decrement nums[curr] by 1. Reverse your movement direction (left becomes right and vice versa). Take a step in your new direction. A selection of the initial position curr and movement direction is considered valid if every element in nums becomes 0 by the end of the process.

Return the number of possible valid selections.

Example 1:​

Input: nums = [1,0,2,0,3]
Output: 2
Explanation:

The only possible valid selections are the following:

Choose curr = 3, and a movement direction to the left.

[1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,1,0,3] -> [1,0,1,0,3] -> [1,0,1,0,2] ->
[1,0,1,0,2] -> [1,0,0,0,2] -> [1,0,0,0,2] -> [1,0,0,0,1] -> [1,0,0,0,1] ->
[1,0,0,0,1] -> [1,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] ->
[0,0,0,0,1] -> [0,0,0,0,0].

Choose curr = 3, and a movement direction to the right.

[1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,2,0,2] -> [1,0,2,0,2] -> [1,0,1,0,2] ->
[1,0,1,0,2] -> [1,0,1,0,1] -> [1,0,1,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] ->
[1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [0,0,0,0,0].

Example 2:​

Input: nums = [2,3,4,0,4,1,0]
Output: 0
Explanation: There are no possible valid selections.

Constraints:​

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100
  • There is at least one element i where nums[i] == 0.

解題思路​

不懂題目在講啥所以先點開 Discussion 看一下
發現有人貼了這張圖

瞬間變得超好懂！

再回來看題目
題目需要找到 curr，並讓 nums[curr] == 0
最後回傳符合需求的 curr 數量

所以在程式裡面可以先定義 result 來記錄符合需求的 curr 數量
再使用 for 迴圈來遍歷 nums，當不是 0 的時候就跳過這次迭代

var countValidSelections = function (nums) {
  let result = 0;

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) continue;
    // TODO
  }

  return result;
};

根據那張圖可以想成要找的其實就是以下三種狀況：

  1. 左右兩邊總和相同
    • 代表不管起始方向是左或右都可以，方塊會被剛好消除光，所以 result += 2
  2. 左邊總和比右邊總和大 1
    • 代表起始方向是左時，方塊會被剛好消除光，但起始方向是右則不行，所以 result += 1
  3. 左邊總和比右邊總和小 1
    • 代表起始方向是右時，方塊會被剛好消除光，但起始方向是左則不行，所以 result += 1

再轉換成程式碼，透過 sumLeft、sumRight 算出左右總和，並篩選出三種狀況與對應的結果

const sumLeft = nums.slice(0, i).reduce((acc, cur) => acc + cur, 0);
const sumRight = nums.slice(i).reduce((acc, cur) => acc + cur, 0);

if (sumLeft === sumRight) result += 2;
if (sumLeft === sumRight - 1) result += 1;
if (sumLeft === sumRight + 1) result += 1;

心得​

做圖人...我的超人...